Search for: All records

Abstract We present an equilibrium model of dynamic trading, learning, and pricing by strategic investors with trading targets and price impact. Since trading targets are private, investors filter the child order flow dynamically over time to estimate the latent underlying parent trading demand imbalance and to forecast its impact on subsequent price-pressure dynamics. We prove existence of an equilibrium and solve for equilibrium trading strategies and prices as the solution to a system of coupled ODEs. Trading strategies are combinations of trading towards investor targets, liquidity provision for other investors’ demands, and speculation based on learning about latent underlying trading-demand imbalances. 

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new approach and use it to prove a Ω(log1.5 n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F2. Proving an ω(lgn) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary . This result also implies the first ω(lgn) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly” simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling” method of Panigrahy et al. 

In the framework of an incomplete financial market where the stock price dynamics are modeled by a continuous semimartingale (not necessarily Markovian), an explicit second-order expansion formula for the power investor’s value function—seen as a function of the underlying market price of risk process—is provided. This allows us to provide first-order approximations of the optimal primal and dual controls. Two specific calibrated numerical examples illustrating the accuracy of the method are also given.